三等分(Leetcode 927)

题目分析

   本题的思路也比较神奇，先给小伙伴提示一下，因为三个部分表示的值一样，且都是二进制，因此三个部分对应1的数量应该相同。

双指针

本题是一个三指针的题目，根据上面的提示，我们可以统计1的总个数，然后看是否是三的倍数。如果不是，一定无法三等分。如果是，我们需要找到第一部分的第一个1(p1)、第二部分的第一个1(p2)和第三部分的第一个1(p3)出现的位置。因为长度是固定的，因此第三部分的值是固定的。就是从第三部分的第一个1一直到数组的最后一位。

假设从p3到最后一位的长度为len。那么剩下就需要看从p1开始，长度为len的区间，是否都和从p2开始，长度为len的区间相等，且和从p3开始长度为len的区间相等。

这里要注意p1 + len必须小于等于p2，p2 + len必须小于等于p3，不能有重叠。

算法的**时间复杂度为O(n)，空间复杂度为O(1)**。

class Solution {
    public int[] threeEqualParts(int[] arr) {
        int sums = Arrays.stream(arr).sum();
        if (sums == 0) {
            return new int[]{0, 2};
        }
        if (sums % 3 != 0) {
            return new int[]{-1, -1};
        }
        int avg = sums / 3;
        int p1 = 0;
        int p2 = 0;
        int p3 = 0;
        int cnt = 0;
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            if (arr[i] == 1) {
                if (cnt == 0) {
                    p1 = i;
                } else if (cnt == avg) {
                    p2 = i;
                } else if (cnt == 2 * avg) {
                    p3 = i;
                }
                cnt++;
            }
        }
        int len = n - p3;
        if (p1 + len > p2 || p2 + len > p3) {
            return new int[]{-1, -1};
        }
        for (int i = 0; i < len; i++) {
            if (arr[p1 + i] != arr[p2 + i]  || arr[p2 + i] != arr[p3 + i]) {
                return new int[]{-1, -1};
            }
        }
        return new int[]{p1 + len - 1, p2 + len};
    }
}

刷题总结

  本题的难度不大，算不上困难的范围，主要是要想到三个相等的部分，其中1的数量也要相同。